package com.yao.code;

import com.yao.tool.Node;
import com.yao.tool.TreeNode;

import java.util.*;

/**
 * @author yaoquanwei
 * @date 2021/8/22 12:17
 */
public class Code210822 {

    Node pre, head;
    private List<List<Integer>> res;

    /**
     * 剑指offer 36.二叉搜索树与双向链表
     *
     * @param root
     * @return
     */
    public Node treeToDoublyList(Node root) {
//        if (root == null) {
//            return root;
//        }
//        Node head = root;
//        Stack<Node> stack = new Stack<>();
//        List<Node> list = new ArrayList<>();
//        stack.add(head);
//        while (!stack.isEmpty() || head != null) {
//            while (head != null) {
//                stack.push(head);
//                head = head.left;
//            }
//            if (!stack.isEmpty()) {
//                head = stack.pop();
//                list.add(head);
//                head = head.right;
//            }
//        }
//        if (list.size() < 2) {
//            return root;
//        }
//        list.get(0).left = list.get(list.size() - 1);
//        list.get(0).right = list.get(1);
//        for (int i = 1; i < list.size() - 1; i++) {
//            list.get(i).left = list.get(i - 1);
//            list.get(i).right = list.get(i + 1);
//        }
//        list.get(list.size() - 1).left = list.get(list.size() - 2);
//        list.get(list.size() - 1).right = list.get(0);
//        return list.get(0);
        // 边界值
        if (root == null) {
            return null;
        }
        dfs(root);

        // 题目要求头尾连接
        head.left = pre;
        pre.right = head;
        // 返回头节点
        return head;
    }

    void dfs(Node cur) {
        // 递归结束条件
        if (cur == null) {
            return;
        }
        dfs(cur.left);
        // 如果pre为空，就说明是第一个节点，头结点，然后用head保存头结点，用于之后的返回
        if (pre != null) {
            if (pre != null) {
                pre.right = cur;
            }
        } else {
            // 如果不为空，那就说明是中间的节点。并且pre保存的是上一个节点，
            // 让上一个节点的右指针指向当前节点
            head = cur;
        }

        // 再让当前节点的左指针指向父节点，也就连成了双向链表
        cur.left = pre;
        // 保存当前节点，用于下层递归创建
        pre = cur;
        dfs(cur.right);
    }

    /**
     * 剑指offer 54.二叉搜索树的第k大节点
     *
     * @param root
     * @param k
     * @return
     */
    public int kthLargest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        int index = 0;
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                root = root.right;
            } else {
                root = stack.pop();
                if (++index == k) {
                    return root.val;
                }
                root = root.left;
            }
        }
        return index;
    }

    /**
     * 剑指offer 34.二叉树中某一值的路径
     *
     * @param root
     * @param sum
     */
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        res = new ArrayList<>();
        backtrack(root, sum, new ArrayList<>());
        return res;
    }

    private void backtrack(TreeNode node, int target, List<Integer> collector) {
        if (node == null) {
            return;
        }
        collector.add(node.val);
        target -= node.val;
        if (target == 0 && node.left == null && node.right == null) {
            res.add(new ArrayList<>(collector));
        } else {
            backtrack(node.left, target, collector);
            backtrack(node.right, target, collector);
        }
        collector.remove(collector.size() - 1);
    }

    public static void main(String[] args) {

    }
}
